public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.repeatedSubstringPattern("abab"));
        System.out.println(s.repeatedSubstringPattern("aba"));
        System.out.println(s.repeatedSubstringPattern("abcabcabcabc"));
        System.out.println(s.repeatedSubstringPattern("abaababaab"));
    }
}


class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = new int[s.length()];
        int i = 0, j = 1;
        while (j < s.length()) {
            while (i > 0 && s.charAt(i) != s.charAt(j)) {
                i = next[i - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                i++;
            }
            next[j++] = i;
        }
        int nextLast = next[s.length() - 1];
        return nextLast > 0 && nextLast % (s.length() - nextLast) == 0;
    }
}